import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Tree {

    public static void main(String[] args) {
        //Integer[] data = new Integer[]{1, 2 ,3, 4,5, null, 6,7,8,null,10,null,null,11,12};
        Integer[] data = new Integer[]{1, 2 ,3, 4,5, null, 6};

        TreeNode root = new TreeNode(data[0]);
        buildTree(root,0,data);
        //print(root);
        //方法1 检测数组非空项是否和生成的二叉树节点相等，相等则认为数组为二叉树数组.
        /*if (checkDataIsTree(root,data)){
            //根据已知数组数据确定每一层对应的数据索引获取对应层的平均数
            //二叉树的层数log2N+1
            int layer =(int) (Math.log(data.length)/Math.log(2)+1);
            //层的平均数数组
            double[] averageLayer = new double[layer];
            for (int i=0;i < layer;i ++) {
                if (i == 0) {
                    //根节点
                    averageLayer[i] = data[i];
                } else {
                    //第i层 数组中起始点儿的索引
                    int layerStartIndex = (int) Math.pow(2,i)-1;
                    //第i层 数组中终点儿的索引
                    int layerEndIndex = (int) Math.pow(2,i) + layerStartIndex-1;
                    //第i层 数组中有效数
                    int validNum = 0;
                    //第i层 所有有效数的合
                    int layerSum = 0;
                    //遍历第i层的数
                    for (int j=layerStartIndex;j <= (layerEndIndex <= (data.length-1) ? layerEndIndex : data.length-1); j++) {
                        if (data[j] != null) {
                            validNum++;
                            layerSum += data[j];
                        }
                    }
                    //System.out.println(i+","+layerEndIndex+","+validNum + "," + layerSum);
                    //第i层数的平均值
                    averageLayer[i] = layerSum*1.0/validNum;
                }
            }
            System.out.println(Arrays.toString(averageLayer));
        }*/

        //方法2 根据二叉树的层遍历获取对应的平均值
        List<ArrayList<Integer>> treeList = layerTraversal(root);
        double[] averageLayer = new double[treeList.size()];
        for (int layer=0;layer<treeList.size();layer ++) {
            //System.out.println(layerList.toString());
            double sum = 0;
            for (Integer value : treeList.get(layer)) {
                sum += value;
            }
            averageLayer[layer] = sum/treeList.get(layer).size();
        }
        System.out.println(Arrays.toString(averageLayer));

    }

    /**
     * 判断数组和二叉树是否合规
     * @param treeNode
     * @param data
     * @return
     */
    private static boolean checkDataIsTree(TreeNode treeNode,Integer[] data) {
        int sumData = 0;
        for (Integer num : data) {
            if (num != null) {
                sumData ++;
            }
        }

        int sumTree = sumTree(treeNode);
        return sumData != 0 && sumData == sumTree;
    }

    /**
     * 获取二叉树的数量
     * @param node
     * @return
     */
    private static int sumTree(TreeNode node) {
        int sum = 0;
        if (node != null) {
            sum ++;
        }
        if (node.left != null) {
            sum += sumTree(node.left);
        }

        if (node.right != null) {
            sum += sumTree(node.right);
        }
        return sum;
    }

    /**
     * 根据给定数组数据创建二叉树
     * @param node
     * @param nodeIndex
     * @param data
     */
    private static void buildTree(TreeNode node,int nodeIndex,Integer[] data) {
        //左子节点的索引
        int leftIndex = 2*(nodeIndex+1) - 1;
        //右子节点的索引
        int rightIndex = leftIndex + 1;
        //拼接左子节点
        if (leftIndex < data.length && data[leftIndex] != null) {
            TreeNode leftNode = new TreeNode(data[leftIndex]);
            node.left = leftNode;
            //System.out.println("left:" + leftNode.value);
            buildTree(leftNode,leftIndex,data);
        }
        //拼接右子节点
        if (rightIndex < data.length && data[rightIndex] != null) {
            TreeNode rightNode = new TreeNode(data[rightIndex]);
            node.right = rightNode;
            //System.out.println("right:" + rightNode.value);
            buildTree(rightNode,rightIndex,data);
        }
    }

    /**
     * 层遍历二叉树
     * @param node
     * @return
     */
    private static List<ArrayList<Integer>> layerTraversal(TreeNode node) {
        //用户缓存每一层的数据值
        List<ArrayList<Integer>> treeList = new ArrayList();
        //根据队列的读取并缓存每一层的节点
        Queue<TreeNode> treeNodes = new LinkedList<>();
        treeNodes.add(node);
        while (true) {
            int size = treeNodes.size();
            if (size <= 0) {
                return treeList;
            }
            ArrayList<Integer> layerData = new ArrayList<>();
            for (int i=0;i<size;i++) {
                TreeNode treeNode = treeNodes.poll();
                if (treeNode.left != null) {
                    treeNodes.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    treeNodes.add(treeNode.right);
                }
                layerData.add(treeNode.value);
            }
            treeList.add(layerData);
        }
    }

    public static class TreeNode {

        int value;

        TreeNode  left;

        TreeNode  right;

        public TreeNode(int value) {
            this.value = value;
        }
    }
}
